package leetCode;

/**
 * LCR 090. 打家劫舍 II
 * https://leetcode.cn/problems/PzWKhm/description/
 */
class Solution5 {
    public int rob(int[] nums) {
        //1、创建dp表
        int len = nums.length;
        if(len == 0) return 0;
        if(len == 1) return nums[0];
        //首房子偷
        int[] f1 = new int[len];
        int[] g1 = new int[len];
        //首房子不偷
        int[] f2 = new int[len];
        int[] g2 = new int[len];
        //初始化，首房子偷的情况
        f1[0] = nums[0];
        g1[0] = 0;
        //填表
        for(int i = 1; i < len - 1; i++) {
            f1[i] = g1[i - 1] + nums[i];
            g1[i] = Math.max(g1[i - 1], f1[i - 1]);
        }
        //初始化，首房子不偷
        f2[0] = 0;
        f2[1] = nums[1];
        g2[0] = 0;
        g2[1] = 0;
        for(int i = 2; i < len; i++) {
            f2[i] = g2[i - 1] + nums[i];
            g2[i] = Math.max(g2[i - 1], f2[i - 1]);
        }
        int max1 = Math.max(f1[len - 2], g1[len - 2]);//首房子偷的情况
        int max2 = Math.max(f2[len - 1], g2[len - 1]);//首房子不偷的情况
        return Math.max(max1, max2);
    }
}